package com.xiaoyu.backtracking;

import java.util.*;

/**
 * @program: DS_and_A
 * @description: 三数之和
 * 给你一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，
 * 使得a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 *
 * 注意：答案中不可以包含重复的三元组。
 *
 * 示例 1：
 *
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 * @author: YuWenYi
 * @create: 2021-05-22 16:39
 **/
public class ThreeSum_15 {

    //使用回溯法固然可行,但是一但数据量太大,那么将直接超时!所以我们需要想别的方法!
    public List<List<Integer>> threeSum1(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length;
        if (len < 3){
            return res;
        }
        Arrays.sort(nums);
        Deque<Integer> path = new ArrayDeque<>();

        dfs(nums, len, 0,0,0,res, path);

        return res;
    }

    public void dfs(int[] nums,int len,int begin,int depth,int target,List<List<Integer>> res,Deque<Integer> path){
        if (depth == 3 && target == 0){
            res.add(new ArrayList<>(path));
            return;
        }
        if (depth > 3){
            return;
        }
        for (int i = begin; i < len; i++) {
            //进行大剪枝
            if (target + nums[i] > 0){
                break;
            }
            //进行剪小枝!!以及避免重复
            if (i > begin && nums[i] == nums[i-1]){
                continue;
            }
            path.push(nums[i]);

            dfs(nums, len, i+1, depth+1, target + nums[i], res, path);

            path.pop();
        }
    }

    //双指针
    public List<List<Integer>> threeSum(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len < 3){
            return res;
        }
        Arrays.sort(nums);
        //排序后如果第一个（最小的）大于0，则和必然大于0，如果最后一个（最大的）小于0同理
        if(nums[0]>0 || nums[len-1]<0){
            return res;
        }

        for (int i = 0; i < len; i++) {
            //若 nums[i]>0nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果
            if (nums[i] > 0){
                break;
            }
            //去重
            if (i > 0 && nums[i] == nums[i-1]){
                continue;
            }
            int left = i + 1 , right = len - 1;
            while (left < right){
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0){
                    //找到结果添加结果集
                    res.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    //如果下一个数何当前数相等,那么直接跳过这个数,即去除重复元素
                    while (left < right && nums[left + 1] == nums[left]) left++;
                    while (left < right && nums[right - 1] == nums[right]) right--;
                    left++;
                    right--;
                }else if (sum > 0){
                    right--;
                }else {
                    left++;
                }
            }
        }
        return res;
    }



    public static void main(String[] args) {
        ThreeSum_15 threeSum_15 = new ThreeSum_15();
        int[] nums = {-1,0,1,2,-1,-4};
        System.out.println(threeSum_15.threeSum(nums));
    }
}
